package com.leetcodehot.problems;

import java.util.*;

public class problems987 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 第一种，将所有的相同的组都收集起来，最暴力的一种，也考察了
     * List<int[]> rv ;
     * rv.sort((a, b)
     * ->
     * a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]
     * );
     */
    /*
    private List<List<Integer>> ans;
    private Map<Integer, List<int[]>> map = new TreeMap<>();
    public void dfs(TreeNode root, int row, int col) {
        if (root == null) {
            return;
        }
        List<int[]> t = map.getOrDefault(col, new ArrayList<>());
        t.add(new int[]{row, root.val});
        map.put(col, t);
        dfs(root.left, row + 1, col - 1);
        dfs(root.right, row + 1, col + 1);
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        ans = new ArrayList<>(map.size());
        dfs(root, 0, 0);
        for (List<int[]> rv : map.values()) {
            rv.sort((a, b)
                    ->
                    a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]
            );

            List<Integer> vals = new ArrayList<>(rv.size());
            for (int[] p : rv) {
                vals.add(p[1]);
            }

            ans.add(vals);
        }
        return ans;
    }
    */

    /**
     * 第二种 更粗暴
     */
    private List<List<Integer>> ans = new ArrayList<>();
    List<int[]> data = new ArrayList<>();

    private void dfs(TreeNode root, int row, int col) {
        if (root == null) {
            return;
        }
        data.add(new int[]{col, row, root.val});
        dfs(root.left, row + 1, col - 1);
        dfs(root.right, row + 1, col + 1);
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        data.sort((a, b) ->
                a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
        int lastCol = Integer.MIN_VALUE;
        for (int[] d : data) {
            if (d[0] != lastCol) {
                lastCol = d[0];
                List<Integer> integers = new ArrayList<>();
                integers.add(d[2]);
                ans.add(integers);
            } else {
                ans.get(ans.size() - 1).add(d[2]);
            }
        }

        return ans;
    }
}
